package week10

// 307. 区域和检索 - 数组可修改
// https://leetcode-cn.com/problems/range-sum-query-mutable/

type NumArray struct {
	tree *SegmentTree
}


func Constructor(nums []int) NumArray {
	arr := NumArray{}
	arr.tree = BuildTree(nums)
	return arr
}


func (this *NumArray) Update(index int, val int)  {
	this.tree.Change(index, val)
}


func (this *NumArray) SumRange(left int, right int) int {
	return this.tree.Query(left, right)
}

type Node struct {
	l, r int
	sum int
}

type SegmentTree struct {
	list []Node
}

func BuildTree(nums []int) *SegmentTree {
	tree := &SegmentTree{}
	tree.list = make([]Node, 4*len(nums))
	tree.build(1, 0, len(nums)-1, nums)
	return tree
}

func (tree *SegmentTree) Change(index, val int) {
	tree.change(1, index, val)
}

func (tree *SegmentTree) Query(left, right int) int {
	return tree.query(1, left, right)
}

func (tree *SegmentTree) build(curr, l, r int, nums []int) {
	tree.list[curr].l = l
	tree.list[curr].r = r
	if l == r {
		tree.list[curr].sum = nums[l]
		return
	}
	var mid = (l + r) / 2
	tree.build(curr * 2, l, mid, nums)
	tree.build(curr * 2 + 1, mid+1, r, nums)
	tree.list[curr].sum = tree.list[curr*2].sum + tree.list[curr*2+1].sum
}

func (tree *SegmentTree) change(curr, index, val int) {
	if tree.list[curr].l == tree.list[curr].r {
		tree.list[curr].sum = val
		return
	}
	var mid = (tree.list[curr].l + tree.list[curr].r) / 2
	if index <= mid {
		tree.change(curr*2, index, val)
	} else {
		tree.change(curr*2+1, index, val)
	}
	tree.list[curr].sum = tree.list[curr*2].sum + tree.list[curr*2+1].sum
}

func (tree *SegmentTree) query(curr, l, r int) int {
	if tree.list[curr].l >= l && tree.list[curr].r <= r {
		return tree.list[curr].sum
	}
	var mid = (tree.list[curr].l + tree.list[curr].r) / 2
	var ans = 0
	if l <= mid {
		ans += tree.query(curr*2, l, r)
	}
	if r > mid {
		ans += tree.query(curr*2+1, l, r)
	}
	return ans
}

/**
 * Your NumArray object will be instantiated and called as such:
 * obj := Constructor(nums);
 * obj.Update(index,val);
 * param_2 := obj.SumRange(left,right);
 */